package graph;

import java.util.ArrayList;
import java.util.List;

public class Prim {
    private  static final int MAX = 100;
    private static final int INF = Integer.MAX_VALUE;

    class Graph{
        char[] vexs = new char[MAX];
        int vexnum;
        int edgenum;
        int[][] matrix = new int[MAX][MAX];

        public Graph(char[] vexs, int vexnum, int edgenum, int[][] matrix) {
            this.vexs = vexs;
            this.vexnum = vexnum;
            this.edgenum = edgenum;
            this.matrix = matrix;
        }
    }

    Graph pGraph;

    class EdgeData{
        char start;
        char end;
        int weight;
    }

    EdgeData edgeData;

    static int getPosition(Graph g,char ch){
        int i;
        for(i = 0;i<g.vexnum;i++){
            if(g.vexs[i]==ch){
                return i;
            }
        }
        return -1;
    }

    Graph createGraph(){
        char[] vexs = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,INF,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        int edgeNum = 0;
        for(int i = 0;i<vexs.length;i++){
            for(int j = 0;j<vexs.length;j++){
                if(i!=j&&matrix[i][j]!=INF){
                    edgeNum++;
                }
            }
        }
        edgeNum/=2;
        Graph graph = new Graph(vexs,vexs.length,edgeNum,matrix);
        return graph;
    }

    void printGraph(Graph graph){
        int i,j;
        System.out.printf("Matrix Graph: \n");
        for(i=0;i<graph.vexnum;i++){
            for(j = 0;j<graph.vexnum;j++){
                System.out.printf(graph.matrix[i][j]+"");
            }
            System.out.printf("\n");
        }
    }

    List<EdgeData> getEdgeData(Graph graph){
        List<EdgeData> edgeList = new ArrayList<>();
        int index = 0;
        for(int i = 0;i<graph.vexnum;i++){
            for(int j = i+1;j<graph.vexnum;j++){
                if(graph.matrix[i][j]!=INF) {
                    EdgeData edgeData = new EdgeData();
                    edgeData.start = graph.vexs[i];
                    edgeData.end = graph.vexs[j];
                    edgeData.weight = graph.matrix[i][j];
                }
            }
        }

        return edgeList;
    }

    void prim(Graph g,int start){
        int min = 0,i = 0,j = 0,k = 0,m = 0,n = 0,sum = 0;
        int index = 0;
        char[] prim = new char[MAX];

        int[] weight = new int[MAX];

        prim[index++] = g.vexs[start];

        for(i = 0;i<g.vexnum;i++){

            if(start==i) continue;

            j = 0;
            k = 0;
            min = INF;
            for(k = 0;k<g.vexnum;k++){

                if(weight[k]>0&&weight[k]<min) {
                    min = weight[k];
                    j = k;
                }
            }
            sum+=min;
            prim[index++] = g.vexs[j];
            weight[j]= 0;


        }
    }
}
